In the Java programming environment (Java is a trademark of Sun Microsystems Inc), programs are generally run on a virtual machine, rather than directly on hardware. Thus a Java program is typically compiled into byte-code form, and then interpreted by the Java virtual machine (VM) into hardware commands for the platform on which the Java VM is executing. The Java environment is further described in many books, for example “Exploring Java” by Niemeyer and Peck, O'Reilly & Associates, 1996, USA, “Java Virtual Machine”, by Meyer and Downing, O'Reilly & Associates, 1997, USA, and “The Java Virtual Machine Specification” by Lindholm and Yellin, Addison-Wedley, 1997, USA.
Java is an object-oriented language. Thus a Java program is formed from a set of class files having methods that represent sequences of instructions. One Java object can call a method in another Java object. A hierarchy of classes can be defined, with each class inheriting properties (including methods) from those classes which are above it in the hierarchy. For any given class in the hierarchy, its descendants (i.e. below it) are called subclasses, whilst its ancestors (i.e. above it) are called superclasses. At run-time classes are loaded into the Java VM by one or more class loaders, which are themselves organised into a hierarchy. Objects can then be created as instantiations of these class files, and indeed the class files themselves are effectively loaded as objects.
A Java class file contains a table of information called the constant pool. The constant pool is a set of constant values referenced by the Java byte-code operators, and also by other elements within the class file. References to constant pool items are done by item index, with the first element in the constant pool getting index value 1. The constant pool index positions are assigned by the appearance order within the class file.
Some of the constant values from a class file need to undergo a transformation from the values extracted from the class file into the values required by the Java VM to execute Java methods. One example of this would be if the constant is a reference to another class, then this would need to be converted from the class name into the actual location of the class in the system. This transformation process is termed resolution, and includes checking that the item to be accessed exists (and if not, potentially loading or creating it), plus checking that access to the relevant item is permitted (e.g. it is not private data within another class). More details about the constant pool and resolution can be found in the above-mentioned book by Meyer and Downing.
The Java VM specification is flexible about the timing of resolution. It is permissible to aggressively resolve constant pool items at load time, providing that any resolution errors are deferred until a constant pool item is used the first time. However, most Java VM implementations employ a lazy resolution strategy, which defers resolution itself until the first use of a constant pool item. This is because lazy resolution strategies tend to have more efficient memory usage, since constants in infrequently used code paths (such as error message literals in error handling code) will only be resolved when (if) required.
To support the resolution process, the internal constant pool format needs to maintain information about the status of each of the constant pool items. The status information contains the constant pool type, as well as a marker flag to control the resolution status. If the flag is set, then this indicates that the corresponding entry in the constant pool has been resolved, thereby allowing its use by Java byte code operations (a constant pool item must be fully resolved before it can be used). Once a constant pool entry is marked as resolved, the entry becomes immutable. At this stage, the Java VM is free to employ optimisation strategies that bypass resolution checks for subsequent usage.
The Java language also supports multiple threads which can run concurrently. As in any concurrent system, it is important to be able to control access to shared resources, to avoid potential conflict between different threads as regards their usage of a particular resource. Java VM implementations of locking are generally based on the concept of monitors which can be associated with objects. A monitor can be used for example to exclusively lock a piece of code in an object associated with that monitor, so that only the thread that holds the lock for that object can run that piece of code—other threads will queue waiting for the lock to become free. The monitor can be used to control access to an object representing either a critical section of code or a resource. Controlling exclusive access to a particular object by Java programs is termed synchronisation.
Returning now to the constant pool, early Java VM implementations represented the constant pool array as a union of constant pool items (a union being a programming construct in the C language). An update to the constant pool therefore required testing of the resolution flag, de-referencing the original constant pool data to resolve the item, resolving the item, setting the new value into the constant pool, and updating the resolved flag to indicate the resolution as complete.
Unfortunately, this process is exposed to potential conflict between two or more threads, which may be utilising the same class simultaneously, and so needing to access the same class data. Thus if a first thread tries to resolve an entry, by acquiring the resolved value, it now needs to (i) set the resolved flag; and (ii) write the resolved value into the constant pool. However, if another thread comes along and tries to read the constant pool entry in-between operations (i) and (ii), it will think that the entry has been resolved according to the flag, when in fact this is not (yet) the case. Nor does reversing the order of operations (i) and (ii) assist, since in this case another thread coming along in-between the two operations will think that the entry has not been resolved, and try to resolve the resolved value, rather than the original entry. In either case an error will result.
To avoid the above conflict, early Java VM implementations protected the resolution process by monitors to ensure that valid information was used to resolve the constant pool item and to make sure that readers see only valid information (of course, once the item has been marked as resolved, the read barriers are no longer required). Effectively, the monitors locked out other threads from operations that needed to be performed atomically (the combination of steps (i) and (ii) above).
These prior art implementations typically used the object monitor of the class owning the constant pool to protect the constant pool data. This is a fairly granular locking mechanism that only blocks access to the object (class) getting updated. Unfortunately however, in Java this same monitor is used to protect synchronised static methods for that class. In practice, it was found that the processing involving the resolution (which may be fairly involved) was prone to race conditions that would cause Java VM deadlock conditions. (Deadlock is where a cyclic chain of dependencies is created that prevents further processing; the simplest example is where thread A owns resource X, and waits on access to resource Y, whilst thread B owns resource Y, and is waiting on access to resource X, in which case neither thread is able to progress).
With the introduction of the Java 2 system (i.e. version 1.2 of the Java VM), the above implementation was replaced by a global monitor to protect constant pool updates. This single global monitor, which covers all the constant pools in the system, resolved the deadlocking problems, since owning this global monitor does not impact usage of synchronised static methods within a class. In addition, it protects against resolution conflict, since only a single thread can try to resolve a constant pool entry at a time.
Unfortunately however, this new approach is not without its own drawbacks. In particular, the use of a single monitor requires all class constant pool activity to be synchronised as a single resource, and this causes scalability problems. Thus in systems running large numbers of threads, especially a heavy multi-tasking application running on multiple processors, fairly heavy contention can occur on the single global monitor, which can impact overall performance. This is compounded by the fact that other subsystems of the Java VM that utilise the constant pool, such as the byte-code verifier and the Just In Time (JIT) compiler, also have to synchronise on the global monitor for access to any of the unresolved constants.
Such problems are exacerbated in the context of an extended Java VM, which allows class sharing between a set of multiple VMs (see “Building a Java virtual machine for server applications: the JVM on OS/390” by Dillenberger et al., IBM Systems Journal, Vol 39/1, January 2000). The idea behind such systems is that a class can be loaded into a single VM, and then accessed and utilised by multiple other VMs, thereby saving memory and start-up time. In such a configuration, there is only a single constant pool, and so the global monitor for constant pool updates will interrupt execution across the entire set of Java virtual machines.
A further problem that arises in a shared classes environment is that resolution updates to the constant pool are not termination safe. Thus a fault in any of the member virtual machines can leave a class constant pool in an inconsistent state, resulting in corruption of the entire set of virtual machines. It is difficult to recover from such error situations, because the resolution mechanism loses information originally read from the class file.